package 动态规划.backageQuestion;

/**
 * 硬币找零问题 给定不同面额的硬币和一个总金额，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 `-1`。
 *
 * 问题分析：
 * 这个问题可以通过动态规划解决，定义一个dp[i] 数组，表示在最大金额为i时，所需硬币的最少个数
 * 初始化状态：dp[0] = 0, 因为目标金额为0不需要硬币
 * 其他状态：   dp[i]  默认可以认为硬币额值都是1的硬币数，
 * 转移方程：  dp[i] = min(dp[i]，dp[i-coins[i]]+1)
 *
 * @Author lf
 * @Date 3/20/2024
 */
public class CoinQuestion {

    public static int coinChange(int[] coins, int amount) {
        int [] dp = new int[amount+1];
        dp[0] = 0;
        // 先初始化默认值，面值都是1的硬币数
        for (int i = 1; i <= amount ; i++) {
            dp[i] = i;
        }
        for (int i = 1; i <= amount ; i++) {
            for (int j = 0; j <coins.length ; j++) {
                //当前硬币的面值小于等于i
                if(coins[j] <= i){
                    dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }

    public static void main(String[] args) {

        int[] coins = {1, 2, 5}; // 硬币面额
        int amount = 11; // 目标金额
        System.out.println("最少硬币数: " + CoinQuestion.coinChange(coins, amount));
    }

}
